package com.kevin.Code.TwoPointer;


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author Vinlee Xiao
 * @Classname ThreeSum
 * @Description Leetcode 15 三数之和 中等难度 二刷
 * @Date 2022/2/19 11:42
 * @Version 1.0
 */
public class ThreeSum {
    public static void main(String[] args) {
        int[] nums = new int[]{0, 0, 0, 0};
        ThreeSum t = new ThreeSum();
        List<List<Integer>> lists = t.threeSum(nums);
        for (List<Integer> list : lists) {
            for (Integer e : list) {
                System.out.print(e + " ");
            }
            System.out.println();
        }
        
    }

    /**
     * 双指针的做法
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        int len = nums.length;
        quickSort(nums, 0, len - 1);
        List<List<Integer>> result = new ArrayList<>();

        for (int first = 0; first < len; first++) {

            //防止重复元素
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            int third = len - 1;
            int target = -nums[first];
            for (int second = first + 1; second < len; second++) {

                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }


                while (second < third && nums[first] + nums[second] > target) {
                    third--;
                }

                if (second == third) {
                    break;
                }

                if (nums[first] + nums[second] == target) {
                    List<Integer> subList = new ArrayList<>();
                    subList.add(nums[first]);
                    subList.add(nums[second]);
                    subList.add(nums[third]);
                    result.add(subList);
                }

            }
        }
        return result;
    }


    public List<List<Integer>> threeSum1(int[] nums) {
        List<Integer> subList = new ArrayList<>();
        List<List<Integer>> result = new ArrayList<>();
        //先对nums进行排序
        quickSort(nums, 0, nums.length - 1);
        //第一层元素
        for (int i = 0; i < nums.length; i++) {

            int first = nums[i];

            int secondIndex = i + 1;
            //防止重复操作
            if (i > 0 && nums[i] == nums[i - 1]) {

                continue;
            }
            int thirdIndex = nums.length - 1;
            while (secondIndex < thirdIndex) {
                int target = -nums[thirdIndex];
                while (secondIndex > i + 1 && secondIndex < thirdIndex && nums[secondIndex] == nums[secondIndex - 1]) {
                    secondIndex++;
                }

                if (secondIndex >= thirdIndex) {
                    break;
                }
                //三个数之和为0
                if (first + nums[secondIndex] == target) {
                    subList.add(first);
                    subList.add(nums[secondIndex]);
                    subList.add(-target);
                    result.add(new ArrayList<>(subList));
                    subList = new ArrayList<>();
                    secondIndex++;
                    thirdIndex = nums.length - 1;
                } else if (first + nums[secondIndex] < target) {
                    secondIndex++;
                } else if (first + nums[secondIndex] > target) {
                    thirdIndex--;
                }
            }
        }

        return result;
    }


    /**
     * 手写快速排序
     * -4 -1 -1 0 1 2
     *
     * @param nums
     * @param low
     * @param high
     */
    private void quickSort(int[] nums, int low, int high) {


        if (high <= low) {
            return;
        }
        int tmp = nums[low];
        int i = low;
        int j = high;
        while (i < j) {

            while (i < j && nums[j] >= tmp) {
                j--;
            }

            while (i < j && nums[i] <= tmp) {
                i++;
            }
            //交换位置i和j的数
            if (i < j) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
        nums[low] = nums[j];
        nums[j] = tmp;
        quickSort(nums, low, j - 1);
        quickSort(nums, j + 1, high);
    }


}
